import java.util.ArrayList;
import java.util.List;
/**
 * Created by L.jp
 * Description:现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。
 * 例如：
 * 给出的字符串为"25525522135",
 * 返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)
 * User: 86189
 * Date: 2022-09-01
 * Time: 21:40
 */
public class Solution {
    static ArrayList<String> ret=new ArrayList<>();
    static StringBuilder tmp=new StringBuilder();
    public static ArrayList<String> restoreIpAddresses (String s) {
        restoreIpAddressesHelper(s,0,0);
        return ret;
    }
    //start指的是每一段ip的起始位置，ipNumber指的是StringBuilder中ip段的数量
    public static void restoreIpAddressesHelper(String s,int start,int ipNumber){
        //如果遍历到了字符串的结尾并且ip段的数量为4，那么就把临时的结果加入结果集
        if(start==s.length() && ipNumber==4){
            ret.add(tmp.toString());
            return;
        }
        // 如果start等于s的长度但是ip段的数量不为4，或者ip段的数量为4但是start小于s的长度，则直接返回
        if((start == s.length() && ipNumber!=4) || (start < s.length() && ipNumber == 4)){
            return;
        }
        // 剪枝：ip段的长度最大是3，并且ip段处于[0,255]
        for(int i=start;i<s.length() && i-start<3 &&
                Integer.parseInt(s.substring(start,i+1))>=0 &&
                Integer.parseInt(s.substring(start,i+1)) <=255;
                i++
        ){
            // 如果ip段的长度大于1，并且第一位为0的话，continue
            if(i+1-start >1 && s.charAt(start)-'0' ==0){
                continue;
            }
            //是合法字符就拼接
            tmp.append(s.substring(start,i+1));
            // 当stringBuilder里的网段数量小于3时，才会加点；
            // 如果等于3，说明已经有3段了，最后一段不需要再加点
            if(ipNumber<3){
                tmp.append(".");
            }
            //加完点之后，就相当于ip段增加一个
            ipNumber++;
            //然后进入下一个位置划分ip
            restoreIpAddressesHelper(s,i+1,ipNumber);
            //遇到不合法的ip段则会跳转到这里，进行回溯
            //首先ip段数量减1
            ipNumber--;
            //然后删除上一次拼接的非法ip段
            //tmp字符串是随着字符串s一步一步拼接来的，start在s的什么位置就在tmp字符串的什么位置，只不过tmp字符串还包括了‘.',
            //因为此时ip段数量已经减了1，所以start+ipNumber刚好就是tmp字符串最后一段ip段的起始位置，不包括最后一个‘.'
            //那么下标i就表示当前在字符串s中认为最后一段ip段的末尾，start和i的位置，在字符串s和tmp是同步的
            //delete的语法规则是删除start~end-1位置的字符串，i+ipNumber+2是跳过最后一个’,'，才能删除最后一个ip段
            tmp.delete(start+ipNumber,i+ipNumber+2);
        }
    }
    
    public static void main(String[] args) {
        String s="25525522135";
        System.out.println(restoreIpAddresses(s));
    }
}
